package com.chenken;

/**
	把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
	输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
	例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。  
	示例 1：
	输入：[3,4,5,1,2]
	输出：1
	示例 2：
	
	输入：[2,2,2,0,1]
	输出：0
	
	来源：力扣（LeetCode） https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
 *
 */
public class FindMinNum {
	
	public static void main(String[] args) {
		int[] numbers = {8,9,10,1,2,2,2,2,2,2};
		System.out.println(new FindMinNum().minArray02(numbers));
	}
	
	/**
	 * 一般解决方案  时间复杂度0(n)
	 * @param numbers
	 * @return
	 */
	public int minArray01(int[] numbers) {
		if(numbers.length == 0) return 0;
		for(int i = 0;i<numbers.length-1;i++) {
			/**
			 * 	前一个与后一个比较，如果前一个比后一个大，返回后一个
			 */
			if(numbers[i]>numbers[i+1]) {	
				return numbers[i+1];
			}
		}
		/**
		   *  全部遍历完，都没有找到，那就是没有前一个比后一个大的数字，就返回numbers[0]
		 */
		return numbers[0];
    }
	
	/**
	 * 二分法  时间复杂度O(logn)
	 * {3,4,5,6,7,8,9,10,1,2}：numbers[middle] > numbers[right]
	 * {8,9,10,1,2,3,4,5,6,7}：numbers[middle] < numbers[right]
	 * {8,9,10,1,2,2,2,2,2,2}:numbers[middle] = numbers[right]
	 */
	public int minArray02(int[] numbers) {
		if(numbers.length == 0) return 0;
		int left = 0,right = numbers.length-1;
		while(left < right) {
			int middle = (left+right) >> 1;
			/**
			 *  说明最小数在(middle+1)-right)
			*/
			if(numbers[middle] > numbers[right]) {
				left = middle + 1;
			}else if(numbers[middle] < numbers[right]){//说明最小数在left - middle
				right = middle;
			}else {	
				/**
				 * 	中间数字等于最右侧数字,right只能--
				 */
				right--;
			}
		}
		return numbers[left];
    }
}
